package com.example.demo.leetcode;

/**
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * 实现 MinStack 类:
 * <p>
 * MinStack() 初始化堆栈对象。<br>
 * void push(int val) 将元素val推入堆栈。<br>
 * void pop() 删除堆栈顶部的元素。<br>
 * int top() 获取堆栈顶部的元素。<br>
 * int getMin() 获取堆栈中的最小元素。<br>
 */
public class _150_最小栈 {

    private class MinStack {

        private ListNode head;

        public MinStack() {
            head = new ListNode();
        }

        /**
         * 入栈
         *
         * @param val
         */
        public void push(int val) {
            ListNode listNode = new ListNode(val);
            ListNode next = head.next;
            if (next == null) {
                listNode.min = val;
                head.next = listNode;
            } else {
                if (val < next.min) {
                    listNode.min = val;
                } else {
                    listNode.min = next.min;
                }
                listNode.next = next;
            }
            head.next = listNode;
        }

        /**
         * 出栈
         */
        public void pop() {
            head = head.next;
        }

        /**
         * 返回栈顶元素
         *
         * @return
         */
        public int top() {
            return head.next.val;
        }

        /**
         * 返回最小值
         *
         * @return
         */
        public int getMin() {
            return head.next.min;
        }

        /**
         * 内部类
         */
        private class ListNode {

            int val;

            int min;

            ListNode next;

            ListNode() {
            }

            ListNode(int val) {
                this.val = val;
            }

            ListNode(int val, ListNode next) {
                this.val = val;
                this.next = next;
            }
        }
    }

}


